package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * http://leetcode.com/onlinejudge
 * 
 * Anagrams
 * 
 * Given an array of strings, return all groups of strings that are anagrams.
 * 
 * Note: All inputs will be in lower-case.
 * 
 * @author yunzhang
 * 
 */
public class Anagrams {
	public ArrayList<String> anagrams(String[] strs) {
		if (strs == null || strs.length == 0)
			return null;

		Map<String, List<String>> map = new HashMap<String, List<String>>();

		for (String str : strs) {
			String sortedStr = ascSort(str);
			if (map.containsKey(sortedStr)) {
				map.get(sortedStr).add(str);
			} else {
				List<String> newList = new ArrayList<String>();
				newList.add(str);

				map.put(sortedStr, newList);
			}
		}

		ArrayList<String> res = new ArrayList<String>();

		for (List<String> list : map.values()) {
			if (list.size() > 1)
				res.addAll(list);
		}

		return res;
	}

	/**
	 * Sorts String in alphabetical order
	 * 
	 * @param str
	 * @return
	 */
	private String ascSort(String str) {
		if (str == null || str.length() < 2)
			return str;

		char[] chs = str.toCharArray();

		for (int i = str.length() - 1; i > 0; --i) {
			for (int j = 0; j < i; ++j) {
				if (chs[j] > chs[j + 1]) {
					char tmp = chs[j + 1];
					chs[j + 1] = chs[j];
					chs[j] = tmp;
				}
			}
		}

		return new String(chs);
	}
}
